package leetcode.editor.cn;

//给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
//
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//
//
// 示例 2：
//
//
//输入：nums = [0]
//输出：[[],[0]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 10
// -10 <= nums[i] <= 10
// nums 中的所有元素 互不相同
//
//
// Related Topics 位运算 数组 回溯 👍 2439 👎 0

import java.util.ArrayList;
import java.util.List;

//Java：子集
public class Subsets{
    public static void main(String[] args) {
        Solution solution = new Subsets().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> cur = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 1; i <= nums.length; i++){
            bachtrack(res, cur,   nums, i,0);
        }

        return res;
    }

        /**
         *
         * @param res

         * @param i  表示子集中元素的个数
         *           * @param i  表示子集中元素的个数
         */
        private void bachtrack(List<List<Integer>> res, List<Integer> cur,  int[] nums, int i,int startIndex) {

            if(cur.size()==i){
                res.add(new ArrayList<>(cur));
                return;
            }
            for (int j = startIndex; j < nums.length; j++) {
                if(!cur.contains(nums[j])&&cur.size()<i){
                    cur.add(nums[j]);
                    bachtrack(res, cur,   nums, i,j+1);
                    cur.remove(cur.size()-1);
                }

            }


        }
}


//leetcode submit region end(Prohibit modification and deletion)

}
